package com.practice.recursive;


public class JobAssignment {
	private int count = 0;
	
	/*********************************************************************
	 * n equal jobs, assign to unlimited identical machines, how many ways?
	 * @param n
	 *********************************************************************/
	public void sameJobSameMachine(int n) {
		int[] a = new int[n];
		count = 0;
		assign(n, n, a, 0);
		System.out.println("f(" + n + ") = " + count);
	}
	
	private void assign(int n, int max, int[] a, int index) {
		if (n == 0) {
			count++;
			return;
		}
		
		if (max > n) max = n;
		for (int i=max; i>0; i--) {
			a[index] = i;
			assign(n-i, i, a, index+1);
		}
	}
	
	/*********************************************************************
	 * n differnt jobs, assign to m identical machines, how many ways?
	 *********************************************************************/
	public int F(int m, int n) {
		int[][] f = new int[m+1][n+1];
		for (int i=0; i<m+1; i++) f[i][0] = 0;
		for (int j=1; j<n+1; j++) f[1][j] = 1;
		
		for (int i=2; i<m+1; i++) {
			for (int j=1; j<n+1; j++) {
				f[i][j] = f[i][j-1]*i + f[i-1][j-1];
			}
		}
		
		int count = 0;
		for (int i=0; i<m+1; i++) count += f[i][n];
		return count;
	}
	
	public static void main(String[] args) {
		JobAssignment j = new JobAssignment();
//		for (int i=1; i<21; i++) {
//			j.assign(i);
//		}
		
		for (int i=1; i<11; i++) System.out.print(j.F(i, i) + " ");
		System.out.println();
	}
}
